
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

/**
 * 
 * @author Dustin Meijer, Alexander Jeurissen
 * @author Hanzehogeschool Groningen, Instituut voor ICT.
 *
 */
public class GetalRij {
	
	private int[] getallen;
	
	public GetalRij( int aantal, int max ){
		// Belangrijke aanname: aantal < max, anders kunnen de getallen niet uniek zijn.
		getallen = new int[aantal];
		vulArrayMetUniekeWaarden( aantal, max );
	}

	private void vulArrayMetUniekeWaarden(int aantal, int max) {
		// Vul een hulplijst met getallen 0, ..., max
		ArrayList<Integer> hulpLijst = new ArrayList<Integer>( max );
		for ( int i=0; i<max; i++){
			hulpLijst.add( i );
		}
		
		// Stop 'aantal' random waarden in getallen
		Random r = new Random();
		for ( int i=0; i<aantal; i++){
			// Het omzetten van Integer naar int gaat sinds Java 1.5 automatisch (unboxing).
			int getal = (Integer) (hulpLijst.remove( r.nextInt( hulpLijst.size())));
			getallen[i] = getal;
		}
	}
	
	public boolean zitErinA( int zoekWaarde ){
		boolean found = false;
		int index = 0;
		while(index < getallen.length){
			if(zoekWaarde == getallen[index]){
				found = true;
			}
			index++;
		}
		return found;
	}

	/**
	 * linear algorithm with break
	 * @param zoekWaarde
	 * @return
	 */
	public boolean zitErinB( int zoekWaarde ){
		boolean found = false;
		int index = 0;
		while(!found && index < getallen.length){
			if(zoekWaarde == getallen[index]){
				found = true;
			}
			index++;
		}
		return found;
	}

	/**
	 * sector search algorithm
	 * @param zoekWaarde
	 * @return
	 */
	public boolean zitErinC( int searchvalue, int sectors ){
		boolean found = false;
		boolean foundable = true;
		
		boolean debug = false;
		
		int start = 0;
		int end = 0;
		int direction = 0;
		int index = 0;
		
		
		int numSectors = sectors; //number of sectors
		double step = 1.0/numSectors; // the size of a sector in % of total array size
		
		//sector indexes
		int sector_start = 0;
		int sector_end = 0;
		
		//sector values
		int sector_start_val = 0;
		int sector_end_val = 0;
		

		if(debug){
			System.err.println("================= SECTOR SEARCH(E) ========================");
			System.err.println("numsectors: "+numSectors);
			System.err.println("sectorsize: "+ (int)(step * 100) + "%" );
			System.err.println();
			System.err.println("----------------------------");
		}
		
		//detect what sector the searchvalue is in
		for(int i = 1; i<=numSectors && !found; i++){
			if(i==1){
				sector_start	=	0;
				sector_end		=	(int)(getallen.length * step);
				
			}else if(i==numSectors){
				sector_start	=	(int)(getallen.length * (step*(i-1)) )+1;
				sector_end		=	getallen.length-1;
			}else{
				sector_start	=	(int)(getallen.length * (step*(i-1)) )+1;
				sector_end		=	(int)(getallen.length * (step*i) );
			}
			sector_start_val = getallen[sector_start];
			sector_end_val	 = getallen[sector_end];
			
			if(debug){
				System.err.println("sector "+i);
				System.err.println("start[index : value]= "+sector_start + " : " + sector_start_val);
				System.err.println("end[index : value]= "+sector_end + " : " + sector_end_val);
				System.err.println("----------------------------");
			}
			
			if(sector_start_val < searchvalue && searchvalue < sector_end_val){
				
				int[] result = getStartEndValues(sector_start,sector_end,sector_start_val,sector_end_val, searchvalue);
				start		=	result[0];
				end			=	result[1];
				direction	=	result[2];
				if(debug)System.err.println("searchvalue is in sector "+i + "\n" + "direction: "+direction);
				break;
			}
		}
		
		
		
		//the search loop
		index=start;
		while(!found && foundable && index != end){
			if(searchvalue == getallen[index]){
				found = true;
			}else if(direction==1 && getallen[index]>searchvalue){
				foundable = false;
			}else if(direction==-1 && getallen[index]<searchvalue){
				foundable = false;
			}
			index += direction;
		}
		
		return found;
		
		
	
		
	}
	
	/**
	 * binary search algorithm 
	 * @param zoekWaarde
	 * @return
	 */
	public boolean zitErinD( int zoekWaarde ){
		boolean found = false;
		
		int highEnd = getallen.length;
		int lowEnd = 0;
		
		int pivot = highEnd /2;
		
		while(!found && highEnd != lowEnd  && highEnd != lowEnd +1){
			if(zoekWaarde != getallen[pivot]){
				if(zoekWaarde < getallen[pivot]){
					highEnd = pivot;
					pivot = ( ( highEnd - lowEnd ) /2 ) + lowEnd;
				}else{
					lowEnd = pivot;
					pivot = ( (highEnd - lowEnd) / 2) + lowEnd ;
				}
			}else{
				found = true;
			}
		}
		return found;
	}
	
	

	
	
	
	
	
	/**
	 * Helper function for quadrant search algorithm.
	 * Detects if search value is closer to the end or the start of the given quadrant.
	 * @param qStart
	 * @param qEnd
	 * @param qStartVal
	 * @param qEndVal
	 * @param searchvalue
	 * @return int[] result contains start and end value;
	 */
	public int[] getStartEndValues(int qStart, int qEnd, int qStartVal, int qEndVal,int searchvalue ){
		//return values
		int[] result = new int[3];
		
		int startDif	=	qStartVal-searchvalue;
		int endDif		=	qEndVal-searchvalue;
		
		if(startDif < 0 )startDif *= -1;
		if(endDif< 0)endDif *=-1;
		
		
		if(startDif > endDif){
			result[0]	=	qEnd;
			result[1]	=	qStart;
			result[2]	=	-1;
		}else{
			result[0]	=	qStart;
			result[1]	=	qEnd;
			result[2]	=	1;
		}
		
		return result;
	}
	
	public void sorteer(){
		Arrays.sort( getallen);
	}
	
	public void print(){
		for( int i=0; i<getallen.length; i++)
			System.out.println(getallen[i]);
	}

}
